package com.fosss.prim;

import java.util.Arrays;

/**
 * 普利姆算法解决修路问题
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        //测试看看图是否创建ok
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000 这个大数，表示两个点不联通
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}};

        Graph graph = new Graph();
        graph.setVerxs(verxs);
        graph.setData(data);
        graph.setWeight(weight);

        MiniTree miniTree = new MiniTree();
        miniTree.setGraph(graph);

        miniTree.showGraph();

        int prim = miniTree.prim(0);
        System.out.println("总路径长度："+prim);

    }
}

/**
 * 创建最小生成树-村庄的图
 */

class MiniTree {
    private Graph graph;
    private int[] visited;//表示是否被访问

    public Graph getGraph() {
        return graph;
    }

    public void setGraph(Graph graph) {
        this.graph = graph;
        this.visited = new int[graph.verxs];
    }


    /**
     * 显示邻接矩阵
     */
    public void showGraph() {
        for (int[] ints : graph.weight) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 编写普利姆算法
     *
     * @param start 从哪个结点开始
     */
    public int prim(int start) {

        visited[start] = 1;//设置为已访问
        int sumWeight=0;
        //一共需要verxs-1条路
        for (int k = 0; k < graph.verxs - 1; k++) {

            int minWeight = 10000;//一个足够大的值
            int h1=-1,h2=-1;
            for (int i = 0; i < graph.verxs; i++) {
                for (int j = 0; j < graph.verxs; j++) {
                    //i是以访问的结点，j是未访问的结点，根据以访问的结点找到距离他最近的未访问的结点，这里是找到最短的路径
                    if (visited[i] == 1 && visited[j] == 0 && minWeight > graph.weight[i][j]) {
                        minWeight = graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            //到这里找到了最短的路径,将该路径对应的结点设置为已访问
            visited[h2]=1;

            //输出信息
            System.out.println("<"+graph.data[h1]+","+graph.data[h2]+">"+" 权值为："+graph.weight[h1][h2]);
            sumWeight+=graph.weight[h1][h2];
        }
        return sumWeight;//返回总权值
    }

}


/**
 * 创建图
 */
class Graph {
    int verxs;//表示结点数量
    char[] data = new char[verxs];//存放结点数据
    int[][] weight = new int[verxs][verxs];//存放边，即邻接矩阵


    public int getVerxs() {
        return verxs;
    }

    public void setVerxs(int verxs) {
        this.verxs = verxs;
    }

    public char[] getData() {
        return data;
    }

    public void setData(char[] data) {
        this.data = data;
    }

    public int[][] getWeight() {
        return weight;
    }

    public void setWeight(int[][] weight) {
        this.weight = weight;
    }


}

















